package cn.cxq.learning.tree;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;

/**
 * 剑指offer
 * 二叉搜索树的第k个结点
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：500547
 * 本题知识点： 树
 *  算法知识视频讲解
 * 题目描述
 * 给定一棵二叉搜索树，请找出其中的第k小的TreeNode结点。
 * 示例1
 * 输入
 * 复制
 * {5,3,7,2,4,6,8},3
 * 返回值
 * 复制
 * {4}
 * 说明
 * 按结点数值大小顺序第三小结点的值为4
 */
public class KthNode {

    @Test
    public void test() {

        TreeNode treeNode1 = new TreeNode(6);
        TreeNode treeNode2 = new TreeNode(1);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(8);
        TreeNode treeNode5 = new TreeNode(7);
        TreeNode treeNode6 = new TreeNode(9);

        treeNode1.left = treeNode2;
        treeNode2.right = treeNode3;
        treeNode1.right = treeNode4;
        treeNode4.left = treeNode5;
        treeNode4.right = treeNode6;

        System.out.println(KthNode(treeNode1,3));
    }

    TreeNode KthNode(TreeNode pRoot, int k) {

        if (k == 0 || pRoot == null) {
            return null;
        }

        ArrayList<TreeNode> treeNodes = new ArrayList<>();

        inorder(pRoot,treeNodes);

        if (treeNodes.size() < k) {
            return null;
        } else {
            return treeNodes.get(k - 1);
        }
    }

    private void inorder(TreeNode treeNode, ArrayList<TreeNode> treeNodes) {
        if (treeNode.left != null) {
            inorder(treeNode.left, treeNodes);
        }

        treeNodes.add(treeNode);

        if (treeNode.right != null) {
            inorder(treeNode.right, treeNodes);
        }
    }


}
